package 哈希表;

public class HashTable <K,V>{
    class HashNode<K,V>{
        private  K key;
        private V value;
        private HashNode<K,V>next;//下一个
        public HashNode(K key,V value){
            this.key=key;
            this.value=value;
            this.next=null;
        }
        public K getKey(){
            return key;
        }
        public V getValue(){
            return value;
        }
        public void setKey(K key){
            this.key=key;
        }
        public void setValue(V value){
            this.value=value;
        }
        public HashNode<K,V> getNext(){
            return next;
        }
        public void setNext(){
            this.next=next;
        }

        public <V, K> void setNext(HashTable<K,V>.HashNode<K,V> kvHashNode) {
        }
    }
    private int getHash(K key){
        return Math.abs(key.hashCode()%SIZE);
    }
    private int SIZE;//数组长度
    private double LOAD_FACTOR=0.75;
    private int size;
    private HashNode<K,V>[] table;//存链表的数组
    public HashTable(int initialCapacity){
        this.SIZE=initialCapacity;
        table=new HashNode[SIZE];
        this.size=0;

    }
    //扩容
    private void resize() {
        int newSize = SIZE * 2; // 新的哈希表大小为原来的两倍
        HashNode<K, V>[] newTable = new HashNode[newSize]; // 创建新的数组

        for (int i = 0; i < SIZE; i++) {
            HashNode<K, V> current = table[i]; // 获取原数组的每个链表的头节点
            while (current != null) {
                K key = current.getKey();
                V value = current.getValue();

                // 根据新的数组大小重新计算哈希值
                int hash = Math.abs(key.hashCode() % newSize);

                // 插入节点到新的数组中
                if (newTable[hash] == null) {//头结点
                    newTable[hash] = new HashNode<>(key, value);
                } else {//非头结点
                    HashNode<K, V> newNode = newTable[hash];
                    while (newNode.getNext() != null) {//找到next不为null的节点进行存储
                        newNode = newNode.getNext();
                    }
                    newNode.setNext(new HashNode<>(key, value));
                }

                current = current.getNext(); // 继续遍历原数组的下一个节点
            }
        }

        table = newTable; // 将引用指向新的数组
        SIZE = newSize; // 更新数组大小
    }
    public void put(K key,V value){
        int hash=getHash(key);
        if(table[hash]==null){
            table[hash]=new HashNode<>(key, value);
        }
        else{
            HashNode<K,V> current=table[hash];
            while(current.getNext()!=null){
                if(current.getKey().equals(key)){
                    current.setValue(value);
                    return;
                }
                current=current.next;
            }
            if(current.getKey().equals(key)){
                current.setValue(value);
            }
            else{
                current.setNext(new HashNode<>(key,value));
            }
        }
        if((double)size/SIZE>LOAD_FACTOR){
            resize();
        }

    }
    public int size() { // 获取哈希表中节点的数量
        int count = 0; // 计数器
        for (int i = 0; i < SIZE; i++) { // 遍历数组
            HashNode<K, V> current = table[i]; // 获取对应索引位置的节点
            while (current != null) { // 遍历链表
                count++; // 计数器加一
                current = current.getNext(); // 继续遍历下一个节点
            }
        }
        return count; // 返回计数器的值，即哈希表中节点的数量
    }
    public V get(K key) { // 根据键获取值
        int hash = getHash(key);
        HashNode<K,V> current = table[hash];//获取对应索引的位置
        while (current != null) { // 遍历链表
            if (current.getKey().equals(key)) { // 如果找到键相同的节点
                return current.getValue(); // 返回对应的值
            }
            current = current.getNext(); // 继续遍历下一个节点
        }
        return null; // 如果未找到对应的键，则返回null
    }
    public void remove(K key) { // 移除指定键的节点
        int hash = getHash(key); // 计算键的哈希值
        HashNode<K, V> previous = null; // 记录前一个节点
        HashNode<K, V> current = table[hash]; // 获取对应索引位置的节点
        while (current != null) { // 遍历链表
            if (current.getKey().equals(key)) { // 如果找到键相同的节点
                if (previous == null) { // 如果当前节点为链表的第一个节点
                    table[hash] = current.getNext(); // 将下一个节点设为新的头节点
                } else { // 如果当前节点不是链表的第一个节点
                    previous.setNext(current.getNext()); // 将上一个节点的next指向当前节点的下一个节点，跳过当前节点
                }
                return;
            }
            previous = current; // 更新前一个节点
            current = current.getNext(); // 继续遍历下一个节点
        }
    }
    public boolean isEmpty() { // 判断哈希表是否为空
        for (int i = 0; i < SIZE; i++) { // 遍历数组
            if (table[i] != null) { // 如果存在非空的节点
                return false; // 表示哈希表不为空
            }
        }
        return true; // 如果数组中所有元素都为空，则返回true表示哈希表为空
    }
}
